package com.code.leetcode._202508;

import java.util.ArrayList;
import java.util.List;

//68 文本左右对齐
public class FullJustify {
    /**
     * 给定一个单词数组words和一个长度maxWidth，重新排版单词，使其成为每行恰好有maxWidth个字符，且左右两端对齐的文本。
     * 你应该使用"贪心算法"来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格' '填充，使得每行恰好
     * 有maxWidth个字符。
     * 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要对于右侧的空格数
     * 文本的最后一行应为左对齐，且单词之间不插入额外的空格。
     * 注意：1、单词是指由非空字符组成的字符序列
     * 2、每个单词的长度大于0，小于等于maxWidth
     * 3、输入单词数字words至少包含一个单词
     * 示例1：输入：words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
     * 输出:
     * [
     * "This    is    an",
     * "example  of text",
     * "justification.  "
     * ]
     * 示例2：输入：words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
     * 输出:
     * [
     * "What   must   be",
     * "acknowledgment  ",
     * "shall be        "
     * ]
     * 解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
     * 因为最后一行应为左对齐，而不是左右两端对齐。
     * 第二行同样为左对齐，这是因为这行只包含一个单词
     * 示例3：输入：words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"]，maxWidth = 20
     * 输出:
     * [
     * "Science  is  what we",
     * "understand      well",
     * "enough to explain to",
     * "a  computer.  Art is",
     * "everything  else  we",
     * "do                  "
     * ]
     **/
    public static void main(String[] args) {
        FullJustify f = new FullJustify();
        System.out.println(f.fullJustify(new String[]{"Science", "is", "what", "we", "understand", "well", "enough", "to", "explain", "to", "a", "computer.", "Art", "is", "everything", "else", "we", "do"}, 20));
    }

    /**
     * 模拟
     * 根据题干描述的贪心算法，对于每一行，我们首先确定最多可以放置多少单词，这样可以得到该行的空格个数，从
     * 而确定该行单词之间的空格个数。
     * 根据题目中填充空格的细节，我们分以下三种情况讨论：
     * 1、当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格；
     * 2、当前行不是最后一行，且不只一个单词：该单词左对齐，在行末填充空格；
     * 3、当前行不是最后一行，且不只一个单词：设当前行单词数位numWords，空格数位numSpaces，我们需要将空格
     * 均匀分配在单词之间，则单词之间应至少由：avgSpaces=numSpaces/(numWords-1)个空格，对于对出来的
     * extraSpaces=numSpace mod(numWords-1)个空格，应填在前extraSpaces个单词之间。
     * 因此，前extraSpaces个单词之间填充avgSpaces+个空格，其余单词之间填充avgSpaces个空格
     */
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> ans = new ArrayList<>();
        int right = 0, n = words.length;
        while (true) {
            int left = right;
            int sumLen = 0;
            // 循环确定当前行可以放多少单词，注意单词之间应至少有一个空格
            while (right < n && sumLen + words[right].length() + right - left <= maxWidth) {
                sumLen += words[right++].length();
            }
            // 当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格
            if (right == n) {
                StringBuffer sb = join(words, left, n, " ");
                sb.append(blank(maxWidth - sb.length()));
                ans.add(sb.toString());
                return ans;
            }
            int numWords = right - left;
            int numSpaces = maxWidth - sumLen;
            // 当前行只有一个单词：该单词左对齐，在行末填充剩余空格
            if (numWords == 1) {
                ans.add(words[left] + blank(numSpaces));
                continue;
            }
            // 当前行不只一个单词
            int avgSpaces = numSpaces / (numWords - 1);
            int extraSpaces = numSpaces % (numWords - 1);
            String sb = join(words, left, left + extraSpaces + 1, blank(avgSpaces + 1)) + // 拼接额外加一个空格的单词
                    blank(avgSpaces) +
                    join(words, left + extraSpaces + 1, right, blank(avgSpaces)); // 拼接其余单词
            ans.add(sb);
        }
    }

    public String blank(int n) {
        return " ".repeat(Math.max(0, n));
    }

    public StringBuffer join(String[] words, int left, int right, String sep) {
        StringBuffer sb = new StringBuffer(words[left]);
        for (int i = left + 1; i < right; ++i) {
            sb.append(sep);
            sb.append(words[i]);
        }
        return sb;
    }
}
